home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / pgp20src.zip / MPILIB.H < prev    next >
C/C++ Source or Header  |  1992-08-05  |  16KB  |  462 lines
  1. /*    C include file for MPI multiprecision integer math routines
  2.  
  3.     Boulder Software Engineering
  4.     3021 Eleventh Street
  5.     Boulder, CO 80304
  6.     (303) 541-0140
  7.  
  8.     (c) Copyright 1986-92 by Philip Zimmermann.  All rights reserved.
  9.     The author assumes no liability for damages resulting from the use 
  10.     of this software, even if the damage results from defects in this 
  11.     software.  No warranty is expressed or implied.  
  12.  
  13.     These routines implement all of the multiprecision arithmetic necessary
  14.     for Rivest-Shamir-Adleman (RSA) public key cryptography, as well as 
  15.     other number-theoretic algorithms such as ElGamal, Diffie-Hellman, 
  16.     or Rabin.
  17.  
  18.     Although originally developed in Microsoft C for the IBM PC, this code 
  19.     contains few machine dependancies.  It assumes 2's complement 
  20.     arithmetic.  It can be adapted to 8-bit, 16-bit, or 32-bit machines, 
  21.     lowbyte-highbyte order or highbyte-lowbyte order.  This version
  22.     has been converted to ANSI C.
  23.  
  24.     Modified 8 Apr 92 - HAJK
  25.     Implement new VAX/VMS primitive support.
  26. */
  27.  
  28. #include "usuals.h"  /* typedefs for byte, word16, boolean, etc. */
  29.  
  30.  
  31. /* #define PORTABLE    */ /* determines if we use C primitives */
  32. /* #define UNIT8    */ /* use 8-bit units */
  33. /* #define UNIT16    */ /* use 16-bit units */
  34. /* #define UNIT32    */ /* use 32-bit units */
  35. /* #define HIGHFIRST    */ /* determines if Motorola or Intel internal format */
  36.  
  37. #ifdef VMS            /* VAX/VMS */
  38. #ifndef PORTABLE
  39. #define UNIT32         /* use 32-bit units */
  40. #endif    /* not PORTABLE */
  41. #endif /* VMS */
  42.  
  43. #ifndef PEASANT /* if not Russian peasant modulo multiply algorithm */
  44. #ifndef MERRITT /* if not Merritt's modmult */
  45. #define UPTON    /* default: use Upton's modmult algorithm */
  46. #endif
  47. #endif
  48.  
  49. #ifndef UNIT32
  50. #ifndef UNIT8
  51. #define UNIT16            /* default--use 16-bit units */
  52. #endif
  53. #endif
  54.  
  55. /***    CAUTION:  If your machine has an unusual word size that is not a
  56.     power of 2 (8, 16, 32, or 64) bits wide, then the macros here that 
  57.     use the symbol "LOG_UNITSIZE" must be changed.
  58. ***/
  59.  
  60. #ifdef UNIT8
  61. typedef unsigned char unit;
  62. typedef signed char signedunit;
  63. #define UNITSIZE 8 /* number of bits in a unit */
  64. #define uppermostbit ((unit) 0x80)
  65. #define BYTES_PER_UNIT 1 /* number of bytes in a unit */
  66. #define units2bits(n) ((n) << 3) /* fast multiply by UNITSIZE */
  67. #define units2bytes(n) (n)
  68. #define bits2units(n) (((n)+7) >> 3)
  69. #define bytes2units(n) (n)
  70. #endif
  71.  
  72. #ifdef UNIT16
  73. typedef word16 unit;
  74. typedef short signedunit;
  75. #define UNITSIZE 16 /* number of bits in a unit */
  76. #define uppermostbit ((unit) 0x8000)
  77. #define BYTES_PER_UNIT 2 /* number of bytes in a unit */
  78. #define units2bits(n) ((n) << 4) /* fast multiply by UNITSIZE */
  79. #define units2bytes(n) ((n) << 1)
  80. #define bits2units(n) (((n)+15) >> 4)
  81. #define bytes2units(n) (((n)+1) >> 1)
  82. #endif
  83.  
  84. #ifdef UNIT32
  85. typedef word32 unit;
  86. typedef long signedunit;
  87. #define UNITSIZE 32 /* number of bits in a unit */
  88. #define uppermostbit ((unit) 0x80000000L)
  89. #define BYTES_PER_UNIT 4 /* number of bytes in a unit */
  90. #define units2bits(n) ((n) << 5) /* fast multiply by UNITSIZE */
  91. #define units2bytes(n) ((n) << 2)
  92. #define bits2units(n) (((n)+31) >> 5)
  93. #define bytes2units(n) (((n)+3) >> 2)
  94. #undef PORTABLE            /* can't use our C versions if 32 bits. */
  95. #endif
  96.  
  97. #define power_of_2(b) ((unit) 1 << (b)) /* computes power-of-2 bit masks */
  98. #define bits2bytes(n) (((n)+7) >> 3)
  99. /*    Some C compilers (like the ADSP2101) will not always collapse constant 
  100.     expressions at compile time if the expressions contain shift operators. */
  101. /* #define uppermostbit power_of_2(UNITSIZE-1) */
  102. /* #define UNITSIZE units2bits(1) */ /* number of bits in a unit */
  103. /* #define bytes2units(n) bits2units((n)<<3) */
  104. /* #define BYTES_PER_UNIT (UNITSIZE >> 3) */
  105. /* LOG_UNITSIZE is the log base 2 of UNITSIZE, ie: 4 for 16-bit units */
  106. /* #define units2bits(n) ((n) << LOG_UNITSIZE) */ /* fast multiply by UNITSIZE */
  107. /* #define units2bytes(n) ((n) << (LOG_UNITSIZE-3)) */
  108. /* #define bits2units(n) (((n)+(UNITSIZE-1)) >> LOG_UNITSIZE) */
  109. /* #define bytes2units(n) (((n)+(BYTES_PER_UNIT-1)) >> (LOG_UNITSIZE-3)) */
  110.  
  111. typedef unit *unitptr;
  112.  
  113.  
  114. /*--------------------- Byte ordering stuff -------------------*/
  115. #ifdef HIGHFIRST
  116.  
  117. /* these definitions assume MSB comes first */
  118. #define pre_higherunit(r)    (--(r))
  119. #define pre_lowerunit(r)    (++(r))
  120. #define post_higherunit(r)    ((r)--)
  121. #define post_lowerunit(r)    ((r)++)
  122. #define bit_index(n)        (global_precision-bits2units((n)+1))
  123. #define lsbptr(r,prec)        ((r)+(prec)-1)
  124. #define make_lsbptr(r,prec)    (r) = lsbptr(r,prec)  
  125. #define unmake_lsbptr(r,prec) (r) = ((r)-(prec)+1) 
  126. #define msbptr(r,prec)        (r)
  127. #define make_msbptr(r,prec)    /* (r) = msbptr(r,prec) */
  128.  
  129. #define rescale(r,currentp,newp) r -= ((newp) - (currentp))
  130. #define normalize(r,prec) \
  131.   { prec = significance(r); r += (global_precision-(prec)); }
  132.  
  133. #else    /* LOWFIRST byte order */
  134.  
  135. /* these definitions assume LSB comes first */
  136. #define pre_higherunit(r)    (++(r))
  137. #define pre_lowerunit(r)    (--(r))
  138. #define post_higherunit(r)    ((r)++)
  139. #define post_lowerunit(r)    ((r)--)
  140. #define bit_index(n)        (bits2units((n)+1)-1)
  141. #define lsbptr(r,prec)        (r)
  142. #define make_lsbptr(r,prec)    /* (r) = lsbptr(r,prec) */  
  143. #define unmake_lsbptr(r,prec) /* (r) = (r) */  
  144. #define msbptr(r,prec)        ((r)+(prec)-1)
  145. #define make_msbptr(r,prec)    (r) = msbptr(r,prec)
  146.  
  147. #define rescale(r,currentp,newp) /* nil statement */
  148. #define normalize(r,prec) prec = significance(r) 
  149.  
  150. #endif    /* LOWFIRST byte order */
  151. /*------------------ End byte ordering stuff -------------------*/
  152.  
  153. /*    Note that the address calculations require that lsbptr, msbptr, 
  154.     make_lsbptr, make_msbptr, mp_tstbit, mp_setbit, mp_clrbit, 
  155.     and bitptr all have unitptr arguments, not byteptr arguments.  */
  156. #define bitptr(r,n) &((r)[bit_index(n)])
  157. #define bitmsk(n) power_of_2((n) & (UNITSIZE-1))
  158.     /* bitmsk() assumes UNITSIZE is a power of 2 */
  159. #define mp_tstbit(r,n) (*bitptr(r,n) &   bitmsk(n))
  160. #define mp_setbit(r,n) (*bitptr(r,n) |=  bitmsk(n))
  161. #define mp_clrbit(r,n) (*bitptr(r,n) &= ~bitmsk(n))
  162. #define msunit(r) (*msbptr(r,global_precision))
  163. #define lsunit(r) (*lsbptr(r,global_precision))
  164. /* #define mp_tstminus(r) ((msunit(r) & uppermostbit)!=0) */
  165. #define mp_tstminus(r) ((signedunit) msunit(r) < 0)
  166.  
  167. /*    MAX_BIT_PRECISION is upper limit that assembly primitives can handle.
  168.     It must be less than 32704 bits, or 4088 bytes.  It should be an
  169.     integer multiple of UNITSIZE*2.
  170. */
  171. #define MAX_BIT_PRECISION 1152
  172. #define MAX_BYTE_PRECISION (MAX_BIT_PRECISION/8)
  173. #define MAX_UNIT_PRECISION (MAX_BIT_PRECISION/UNITSIZE)
  174.  
  175.  
  176. /*************** multiprecision library primitives ****************/
  177. #ifdef PORTABLE    /* using slow portable C primitives */
  178.  
  179. #define set_precision(prec) (global_precision = (prec))
  180.  
  181. #else    /* not PORTABLE - not using portable C primitives */
  182. /*
  183.     The following primitives should be coded in assembly.
  184.     Functions P_ADDC, P_SUBB, and P_ROTL return a carry flag as their
  185.     functional return, and the result of the operation is placed in r1.
  186.     These assembly primitives are externally defined, unless PORTABLE 
  187.     is defined.
  188. */
  189.  
  190. #ifdef VMS
  191. /*
  192.     Define Assembler Prims With Lowercase Names To Prevent GCC hacking
  193.     them
  194. */
  195. #define P_SETP p_setp
  196. #define P_ADDC p_addc
  197. #define P_SUBB p_subb
  198. #define P_ROTL p_rotl
  199.  
  200. #endif /* VMS */
  201.  
  202. void P_SETP(short nbits);
  203.     /* sets working precision to specified number of bits. */
  204.  
  205. boolean P_ADDC(unitptr r1, unitptr r2, boolean carry);
  206.     /* multiprecision add with carry r2 to r1, result in r1 */
  207.  
  208. boolean P_SUBB(unitptr r1, unitptr r2, boolean borrow);
  209.     /* multiprecision subtract with borrow, r2 from r1, result in r1 */
  210.  
  211. boolean P_ROTL(unitptr r1, boolean carry);
  212.     /* multiprecision rotate left 1 bit with carry, result in r1. */
  213.  
  214. /* Define C primitive names as the equivalent calls to assembly primitives. */
  215. #define set_precision(prec)    P_SETP(units2bits(global_precision=(prec)))
  216. #define mp_addc        P_ADDC
  217. #define mp_subb        P_SUBB
  218. #define mp_rotate_left     P_ROTL
  219.  
  220. #ifdef VMS
  221.  
  222. short p_cmp(register unitptr r1,register unitptr r2);
  223.     /* Compares registers *r1, *r2, and returns -1, 0, or 1 */
  224.  
  225. #define mp_compare p_cmp
  226.  
  227. #endif /* VMS */
  228.  
  229. #endif    /* not PORTABLE */
  230. /************** end of primitives that should be in assembly *************/
  231.  
  232. #ifdef PEASANT
  233.  
  234. /* Define C names for Russian peasant modmult primitives. */
  235. #define stage_modulus stage_peasant_modulus
  236. #define mp_modmult peasant_modmult
  237. #define modmult_burn peasant_burn
  238.  
  239. #endif    /* PEASANT */
  240.  
  241. #ifdef MERRITT
  242. /* Define C names for Merritt's modmult primitives. */
  243. #define stage_modulus stage_merritt_modulus
  244. #define mp_modmult merritt_modmult
  245. #define modmult_burn merritt_burn
  246.  
  247. #endif    /* MERRITT */
  248.  
  249. #ifdef UPTON
  250. /* Define C names for Upton's modmult primitives. */
  251. #define stage_modulus stage_upton_modulus
  252. #define mp_modmult upton_modmult
  253. #define modmult_burn upton_burn
  254.  
  255. #endif    /* UPTON */
  256.  
  257.  
  258. #define mp_shift_left(r1) mp_rotate_left(r1,(boolean)0)
  259.     /* multiprecision shift left 1 bit */
  260.  
  261. #define mp_add(r1,r2) mp_addc(r1,r2,(boolean)0)
  262.     /* multiprecision add with no carry */
  263.  
  264. #define mp_sub(r1,r2) mp_subb(r1,r2,(boolean)0)
  265.     /* multiprecision subtract with no borrow */
  266.  
  267. #define mp_abs(r) (mp_tstminus(r) ? (mp_neg(r),TRUE) : FALSE)
  268.  
  269. #define msub(r,m) if (mp_compare(r,m) >= 0) mp_sub(r,m)
  270.     /* Prevents r from getting bigger than modulus m */
  271.  
  272. #define testeq(r,i)    \
  273.     ( (lsunit(r)==(i)) && (significance(r)<=1) )
  274.  
  275. #define testne(r,i)    \
  276.     ( (lsunit(r)!=(i)) || (significance(r)>1) )
  277.  
  278. #define testge(r,i)    \
  279.     ( (lsunit(r)>=(i)) || (significance(r)>1) )
  280.  
  281. #define testle(r,i)    \
  282.     ( (lsunit(r)<=(i)) && (significance(r)<=1) )
  283.  
  284. #define mp_square(r1,r2) mp_mult(r1,r2,r2)
  285.     /* Square r2, returning product in r1 */
  286.  
  287. #define mp_modsquare(r1,r2) mp_modmult(r1,r2,r2)
  288.     /* Square r2, returning modulo'ed product in r1 */
  289.  
  290. #define countbytes(r) ((countbits(r)+7)>>3)
  291.  
  292. /*    SLOP_BITS is how many "carry bits" to allow for intermediate 
  293.     calculation results to exceed the size of the modulus.
  294.     It is used by modexp to give some overflow elbow room for
  295.     modmult to use to perform modulo operations with the modulus. 
  296.     The number of slop bits required is determined by the modmult 
  297.     algorithm.  The Russian peasant modmult algorithm only requires 
  298.     1 slop bit, for example.  Note that if we use an external assembly
  299.     modmult routine, SLOP_BITS may be meaningless or may be defined in a
  300.     non-constant manner.
  301. */
  302. #ifdef MERRITT    /* use Merritt's modmult algorithm */
  303. #define SLOP_BITS (UNITSIZE+1)
  304. #define MERRITT_KEY    /* cause keygen to generate unnormalized keys */
  305. #endif    /* MERRITT */
  306. #ifdef PEASANT    /* use Russian peasant modmult algorithm */
  307. #define SLOP_BITS 1
  308. #endif /* PEASANT */
  309. #ifdef UPTON    /* use Upton's modmult algorithm */
  310. /* Not clear what SLOP_BITS needs to be */
  311. #define SLOP_BITS UNITSIZE
  312. #endif /* UPTON */
  313.  
  314. /* global_precision is the unit precision last set by set_precision */
  315. extern short global_precision;
  316.  
  317.  
  318.  
  319. /*    The "bit sniffer" macros all begin sniffing at the MSB.
  320.     They are used internally by all the various multiply, divide, 
  321.     modulo, exponentiation, and square root functions.
  322. */
  323. #define sniff_bit(bptr,bitmask)    (*(bptr) & bitmask)
  324.  
  325. #define init_bitsniffer(bptr,bitmask,prec,bits) \
  326. { normalize(bptr,prec); \
  327.   if (!prec) \
  328.     return(0); \
  329.   bits = units2bits(prec); \
  330.   make_msbptr(bptr,prec); bitmask = uppermostbit; \
  331.   while (!sniff_bit(bptr,bitmask)) \
  332.   { bitmask >>= 1; bits--; \
  333.   } \
  334. }
  335.  
  336. #define bump_bitsniffer(bptr,bitmask) \
  337. { if (!(bitmask >>= 1)) \
  338.   { bitmask = uppermostbit; \
  339.     post_lowerunit(bptr); \
  340.   } \
  341. }
  342.  
  343. /* bump_2bitsniffers is used internally by mp_udiv. */
  344. #define bump_2bitsniffers(bptr,bptr2,bitmask) \
  345. { if (!(bitmask >>= 1)) \
  346.   { bitmask = uppermostbit; \
  347.     post_lowerunit(bptr); \
  348.     post_lowerunit(bptr2); \
  349.   } \
  350. }
  351.  
  352. /* stuff_bit is used internally by mp_udiv and mp_sqrt. */
  353. #define stuff_bit(bptr,bitmask)    *(bptr) |= bitmask
  354.  
  355.  
  356.  
  357. #ifdef PORTABLE    /* these slow C primitives should be recoded in assembly */
  358.  
  359. boolean mp_addc
  360.     (register unitptr r1,register unitptr r2,register boolean carry);
  361.     /* multiprecision add with carry r2 to r1, result in r1 */
  362.  
  363. boolean mp_subb
  364.     (register unitptr r1,register unitptr r2,register boolean borrow);
  365.     /* multiprecision subtract with borrow, r2 from r1, result in r1 */
  366.  
  367. boolean mp_rotate_left(register unitptr r1,register boolean carry);
  368.     /* multiprecision rotate left 1 bit with carry, result in r1. */
  369.  
  370. #endif    /* PORTABLE */
  371.  
  372. void mp_shift_right_bits(register unitptr r1,register short bits);
  373.     /* multiprecision shift right bits, result in r1. */
  374.  
  375. short mp_compare(register unitptr r1,register unitptr r2);
  376.     /* Compares registers *r1, *r2, and returns -1, 0, or 1 */    
  377.  
  378. boolean mp_inc(register unitptr r);
  379.     /* Increment multiprecision integer r. */
  380.  
  381. boolean mp_dec(register unitptr r);
  382.     /* Decrement multiprecision integer r. */
  383.  
  384. void mp_neg(register unitptr r);
  385.     /* Compute 2's complement, the arithmetic negative, of r */
  386.  
  387. #ifdef VAXC
  388. /*
  389.  * A VAX is a CISC machine. Unfortunately C is at to low a level to use
  390.  * many of the instruction set enhancements so we define some macros
  391.  * here that implement fast moves and fast zero fills with single
  392.  * instructions.
  393.  */
  394.  
  395. #pragma builtins
  396. #define mp_move( dst, src)      _MOVC3( global_precision*4, (char *) src, (char *) dst)
  397. #define unitfill0( r, unitcount) _MOVC5( 0, (char *) 0, 0, unitcount*4, (char *) r)
  398. #define mp_burn(r) _MOVC5(0, (char *) 0, 0, global_precision*4, (char *) r)
  399. #define mp_init0(r) mp_burn(r)    /* Just for documentation purposes */
  400.  
  401. #else /* VAXC */
  402.  
  403. void mp_move(register unitptr dst,register unitptr src);
  404.  
  405. void unitfill0(unitptr r,word16 unitcount);
  406. #define mp_burn(r) mp_init(r,0) /* for burning the evidence */
  407. #define mp_init0(r) mp_init(r,0)
  408.  
  409. #endif /* VAXC */
  410.  
  411. void mp_init(register unitptr r, word16 value);
  412.     /* Init multiprecision register r with short value. */
  413.  
  414. short significance(register unitptr r);
  415.     /* Returns number of significant units in r */
  416.  
  417. int mp_udiv(register unitptr remainder,register unitptr quotient,
  418.     register unitptr dividend,register unitptr divisor);
  419.     /* Unsigned divide, treats both operands as positive. */
  420.  
  421. int mp_recip(register unitptr quotient,register unitptr divisor);
  422.     /* Compute reciprocal as 1/divisor.  Used by faster modmult. */
  423.  
  424. int mp_div(register unitptr remainder,register unitptr quotient,
  425.     register unitptr dividend,register unitptr divisor);
  426.     /* Signed divide, either or both operands may be negative. */
  427.  
  428. word16 mp_shortdiv(register unitptr quotient,
  429.     register unitptr dividend,register word16 divisor);
  430.     /* Returns short remainder of unsigned divide. */
  431.  
  432. int mp_mod(register unitptr remainder,
  433.     register unitptr dividend,register unitptr divisor);
  434.     /* Unsigned divide, treats both operands as positive. */
  435.  
  436. word16 mp_shortmod(register unitptr dividend,register word16 divisor);
  437.     /* Just returns short remainder of unsigned divide. */
  438.  
  439. int mp_mult(register unitptr prod,
  440.     register unitptr multiplicand,register unitptr multiplier);
  441.     /* Computes multiprecision prod = multiplicand * multiplier */
  442.  
  443. int stage_modulus(unitptr n);
  444.     /* Must pass modulus to stage_modulus before calling modmult. */
  445.  
  446. int mp_modmult(register unitptr prod,
  447.     unitptr multiplicand,register unitptr multiplier);
  448.     /* Performs combined multiply/modulo operation, with global modulus */
  449.  
  450. int countbits(unitptr r);
  451.     /* Returns number of significant bits in r. */
  452.  
  453. int mp_modexp(register unitptr expout,register unitptr expin,
  454.     register unitptr exponent,register unitptr modulus);
  455.     /* Combined exponentiation/modulo algorithm. */
  456.  
  457. int rsa_decrypt(unitptr M, unitptr C,
  458.     unitptr d, unitptr p, unitptr q, unitptr u);
  459.     /* Uses Chinese Remainder Theorem shortcut for RSA decryption. */
  460.  
  461. /****************** end of MPI library ****************************/
  462.